# -*- coding:utf-8 -*-


class Solution:
    def partition(self, arr, begin, end):
        if not arr:
            return -1
        left = begin
        right = end
        node = arr[left]
        while left < right:
            while right > left and arr[right] <= node:
                right -= 1
            arr[left] = arr[right]
            while right > left and arr[left] >= node:
                left += 1
            arr[right] = arr[left]
        arr[left] = node

        return left

    def lpartition(self, arr, begin, end):
        left = begin + 1
        right = begin + 1
        node = arr[begin]
        while right <= end:
            if arr[right] > node:
                arr[left], arr[right] = arr[right], arr[left]
                left += 1
                right += 1
            else:
                right += 1
        arr[left - 1], arr[begin] = arr[begin], arr[left - 1]
        return left - 1

    def findKth(self, a, n, K):
        begin = 0
        end = n - 1

        while 1:
            pos = self.lpartition(a, begin, end)
            print(pos)
            if pos == K - 1:
                return a[pos]
            elif pos > K - 1:
                end = pos - 1
            else:
                begin = pos + 1

        return -1


a = [
    1332802,
    1177178,
    1514891,
    871248,
    753214,
    123866,
    1615405,
    328656,
    1540395,
    968891,
    1884022,
    252932,
    1034406,
    1455178,
    821713,
    486232,
    860175,
    1896237,
    852300,
    566715,
    1285209,
    1845742,
    883142,
    259266,
    520911,
    1844960,
    218188,
    1528217,
    332380,
    261485,
    1111670,
    16920,
    1249664,
    1199799,
    1959818,
    1546744,
    1904944,
    51047,
    1176397,
    190970,
    48715,
    349690,
    673887,
    1648782,
    1010556,
    1165786,
    937247,
    986578,
    798663,
]
n = 49
K = 24
s = Solution()
#  print(dir(a))
print(s.findKth(a, n, K))
